package com.study.bniarysearch;

import com.study.sort.MergeSort;

import java.util.Arrays;

public class BinarySearch {

    public static void main(String[] args) {
        int[] ints = getInts(10);

        MergeSort mergeSort = new MergeSort();
        ints = mergeSort.run(ints.clone());

        System.out.println(Arrays.toString(ints));

        int target = 20;
//        int target = ints[2];
        System.out.println("目标值: " + target);
//        int index = bSearch(ints, target, 0, ints.length - 1);
        int index = bSearch1(ints, target);
        String x = index < 0 ? "不存在" : "int[" + index + "]=" + ints[index];
        System.out.println("结果: " + x);
    }


    /**
     * 二分查找
     * 循环版
     */
    public static int bSearch1(int[] array, int target) {
        int l = 0;
        int r = array.length;

        int i = l;
        while (array[i] != target && l <= r) {
            if (array[i] < target) {
                l = i + 1;
            } else {
                r = i - 1;
            }
            i = (r + l) / 2;
        }

        return array[i] == target ? i : -1;
    }

    /**
     * 二分查找
     * 递归版
     */
    public static int bSearch(int[] array, int target, int l, int r) {
        if (l >= r) {
            return array[l] == target ? l : -1;
        }
        int i = (l + r) / 2;
        if (array[i] > target) {
            return bSearch(array, target, l, i - 1);
        } else if (array[i] < target) {
            return bSearch(array, target, i + 1, r);
        } else {
            return i;
        }
    }

    public static int[] getInts(int length) {
        int[] ints = new int[length];

        for (int i = 0; i < length; i++) {
            ints[i] = (int) (Math.random() * 100);
        }
        return ints;
    }
}
